/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 归并;

/**
 * @Description 归并排序
 * 利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略
 * （分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
 * @Author 俊昭
 * @Date 2022/5/1
 */
public class Merge {
    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int left, int right) {
        if (left < right) {
            //找出中间索引 分！
            int center = (left + right) / 2;
            sort(arr, left, center);
            sort(arr, center + 1, right);
            //合并 治！
            merge(arr, left, center, right);
        }
    }

    /**
     * @description 归并
     * @author 俊昭
     * @date 2022/5/1
     */
    private static void merge(int[] arr, int left, int center, int right) {
        int[] tempArr = new int[arr.length];
        int i = left;
        int templeft = left;
        int mid = center + 1;
        while (left <= center && right >= mid) {
            if (arr[left] <= arr[mid]) {
                tempArr[templeft] = arr[left];
                templeft++;
                left++;
            } else {
                tempArr[templeft] = arr[mid];
                templeft++;
                mid++;
            }
        }
        while (mid <= right) {
            tempArr[templeft] = arr[mid];
            templeft++;
            mid++;
        }
        while (left <= center) {
            tempArr[templeft] = arr[left];
            templeft++;
            left++;
        }
        // 赋值
        while (i <= right) {
            arr[i] = tempArr[i];
            i++;
        }
    }
}
